Computer systems which have either single or multiple central processing units (CPU's) coupled to an associated memory system often perform queue operations to organize related blocks of stored data. Queues are data structures used to organize sets of data blocks in memory by means of pointers associated with each data block in the queue. In the case of "singly linked" queues, these pointers reference the addresses of successive data blocks, or "members", in the queue. A "singly-linked" queue is a queue in which each member includes a pointer to its successor in the queue. In this context "enqueuing" means adding a data block to the queue, and "dequeuing" means removing a data block from the beginning of the queue.
CPU's perform queue manipulations by executing a sequence of read and write operations which are issued to the memory system. Some CPU's include such manipulations in their instruction repertoire, while others require explicit programming of the individual steps involved. In either case, the data which is read and written during the queue manipulation passes into and out of the CPU. In systems with multiple CPU's served by a single memory controller, the CPU's must take explicit actions to assure that queue manipulations are "atomic" sequences. "Atomic" sequences provide exclusive access to the memory controller when one of the CPU's begins a queue manipulation until that CPU finishes the queue manipulation. Otherwise, the sequence of operations necessary to perform a proper queue modification by one CPU would be corrupted by the operations of another CPU simultaneously modifying the same queue. This can leave the queue in an inconsistent state.
One method of assuring such atomic sequences for the queue manipulation is to use data semaphores to implement an exclusive access policy. The semaphores are used to lock access to an associated queue, a section of the memory, or all of the memory. Another method is to supply a hardware signal that is asserted to request the memory controller to provide exclusive access to the memory or a section of the memory when a CPU is to execute queue manipulation instructions. This method requires that all of the CPU's in the system have compatible exclusive-access requesting mechanisms to implement a collaborative exclusive-access policy. This method also requires that the memory controller be designed to interpret the exclusive-access requesting signals asserted by the CPU's.